home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / BASE_HAS.C < prev    next >
C/C++ Source or Header  |  1992-08-19  |  14KB  |  335 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 06/06/89 -- Initial implementation
  13. // Updated: LGO 09/19/89 -- Split into one file per method
  14. // Updated: VDN 02/21/92 -- New lite version
  15. // 
  16. //
  17. // This file contains member and  friend function implementation code  for the
  18. // Base Hash   Table class  defined  in the  Base_Hash.h  header file.   Where
  19. // appropriate and  possible,  interfaces   to, and   us of, existing   system
  20. // functions has been incorporated.  An overview of  the structure of the Base
  21. // Hash Table class, along with a synopsis of each member and friend function,
  22. // can be found in the Base_Hash_Table.h header file.
  23.  
  24. #include <cool/Base_Hash.h>
  25.  
  26. #include <string.h>                // for strcmp()
  27.  
  28. long hash_primes[] = {3, 7, 13, 19, 29, 41, 53, 67, 83, 97, 113, 137,
  29.                       163, 191, 223, 263, 307, 349, 401, 461, 521,
  30.               653, 719, 773, 839, 911, 983, 1049, 1123, 1201,
  31.               1279, 1367, 1459, 1549, 1657, 1759, 1861, 1973,
  32.               2081, 2179, 2281, 2383, 2503, 2617, 2729, 2843,
  33.               2963, 3089, 3203, 3323, 3449, 3571, 3697, 3833,
  34.               3967, 4099, 4241, 4391, 4549, 4703, 4861, 5011,
  35.               5171, 5333, 5483, 5669, 5839, 6029, 6197, 6361,
  36.               6547, 6761, 6961, 7177, 7393, 7517, 7727, 7951,
  37.               8101, 8209, 16411, 32771, 65537, 131301, 262147,
  38.               524287};
  39.  
  40. // CoolBase_Hash_Table -- Simple constructor with no arguments that creates a hash
  41. //               table object with the minimal prime number of buckets and
  42. //               uses the default hash function.
  43. // Input:        None
  44. // Output:       None
  45.  
  46. CoolBase_Hash_Table::CoolBase_Hash_Table () {
  47.   this->growth_ratio = 0.0;            // Grow to next prime number
  48.   this->entry_count = 0;            // No entries in table
  49.   this->current_bucket = 0;            // Index to number of buckets
  50.   this->curpos = INVALID;            // Invalidate current position
  51.   long prime = hash_primes[this->current_bucket]; // Get prime number 
  52.   this->items_in_buckets = new unsigned char[prime]; // Counts items in buckets
  53.   for (long i = 0; i < prime; i++)        // For each bucket count
  54.     this->items_in_buckets[i] = 0;        // Initialize to zero
  55. }
  56.  
  57. // CoolBase_Hash_Table -- Simple constructor with one argument that creates a hash
  58. //               table object with the minimal prime number of buckets that
  59. //               holds some user-supplied number of items and uses the default
  60. //               hash function.
  61. // Input:        Minimal number of items table must hold
  62. // Output:       None
  63.  
  64. CoolBase_Hash_Table::CoolBase_Hash_Table (long n) {
  65.   this->growth_ratio = 0.0;            // Grow to next prime number
  66.   this->entry_count = 0;            // No entries in table
  67.   this->current_bucket = 0;            // Index to number of buckets
  68.   this->curpos = INVALID;            // Invalidate current position
  69.   while (hash_primes[this->current_bucket]*BUCKET_SIZE < n) // Find prime big
  70.     this->current_bucket++;                // ... enough for number items
  71.   long prime = hash_primes[this->current_bucket]; // Get prime number 
  72.   this->items_in_buckets = new unsigned char[prime]; // Counts items in buckets
  73.   for (long i = 0; i < prime; i++)         // For each bucket count
  74.     this->items_in_buckets[i] = 0;         // Initialize to zero
  75. }
  76.  
  77.  
  78. // CoolBase_Hash_Table -- constructor that takes a reference to an existing hash table
  79. //               and duplicates both its size and contents
  80. // Input:        Reference to hash table object
  81. // Output:       None
  82.  
  83. CoolBase_Hash_Table::CoolBase_Hash_Table (const CoolBase_Hash_Table& h) {
  84.   this->growth_ratio = h.growth_ratio;        // Grow to next prime number
  85.   this->entry_count = h.entry_count;        // No entries in table
  86.   this->current_bucket = h.current_bucket;    // Index to number of buckets
  87.   this->curpos = INVALID;            // Invalidate current position
  88.   long prime = hash_primes[this->current_bucket]; // Get prime number 
  89.   this->items_in_buckets = new unsigned char[prime]; // Counts items in buckets
  90.   for (long i = 0; i < prime; i++)        // For each bucket count
  91.     this->items_in_buckets[i] = h.items_in_buckets[i]; // Copy item count
  92. }
  93.  
  94.  
  95. // ~CoolBase_Hash_Table -- Destructor for the CoolBase_Hash_Table class
  96. // Input:         this*
  97. // Output:        None
  98.  
  99. CoolBase_Hash_Table::~CoolBase_Hash_Table () {
  100.   delete [] this->items_in_buckets;        // Free bucket count storage
  101. }
  102.  
  103.  
  104. // Operator= -- Assignment of one hash table to another duplicating size and
  105. //              contents and returning old storage
  106. // Input:       Reference to hash table object
  107. // Output:      Reference to new hash table object
  108.  
  109. CoolBase_Hash_Table& CoolBase_Hash_Table::operator= (const CoolBase_Hash_Table& h) {
  110.   this->growth_ratio = h.growth_ratio;        // Grow to next prime number
  111.   this->entry_count = h.entry_count;        // No entries in table
  112.   this->current_bucket = h.current_bucket;    // Index to number of buckets
  113.   long prime = hash_primes[this->current_bucket]; // Get prime number
  114.   delete [] this->items_in_buckets;        // Return old count storage
  115.   this->items_in_buckets = new unsigned char[prime]; // Counts items in buckets
  116.   for (long i = 0; i < prime; i++)         // For each bucket count
  117.     this->items_in_buckets[i] = h.items_in_buckets[i]; // Copy item count
  118.   this->curpos = INVALID;                   // Invalidate current position
  119.   return *this;                    // Return reference
  120. }
  121.  
  122. // next -- Increment current position. If INVALID, set to first
  123. // Input:  this*
  124. // Output: TRUE/FALSE
  125.  
  126. Boolean CoolBase_Hash_Table::next () {
  127.   long prime = this->get_bucket_count ();    // Prime number of buckets
  128.   if (this->curpos == INVALID) {        // If INVALID current position
  129.     if (this->entry_count == 0)            // If no entries in table
  130.       return FALSE;                // Return failure
  131.     for (long i = 0; i < this->get_bucket_count(); i++)    // For each bucket
  132.       if (this->get_count_in_bucket(i) != 0)    // If the bucket has an item
  133.     break;
  134.     this->curpos = SET_BUCKET_NUMBER(i);    // Set bucket number
  135.     this->curpos |= SET_BUCKET_INDEX(0);    // Set index into bucket
  136.     return TRUE;                // Return success
  137.   }
  138.   else if (TRAVERSED(this->curpos))        // If already traversed set
  139.     return FALSE;                // Inidicate failure
  140.   else {
  141.     long hash = BUCKET_NUMBER(this->curpos);    // Get bucket number
  142.     long index = BUCKET_INDEX(this->curpos);    // Get index in bucket
  143.     if (++index < this->get_count_in_bucket(hash)){// If more items in bucket
  144.       this->curpos = SET_BUCKET_NUMBER(hash);       // Update bucket hash bits
  145.       this->curpos |= SET_BUCKET_INDEX(index);  // Update bucket index bits
  146.       return TRUE;                // And return success
  147.     }
  148.     for (long i = hash+1; i < prime; i++)    // For remaining buckets
  149.       if (this->get_count_in_bucket(i) != 0)    // If the bucket has item
  150.     break;
  151.     if (i == prime) {                // If no more items
  152.       this->curpos = INVALID;            // Invalidate pointer
  153.       return FALSE;                // Return failure
  154.     }
  155.     this->curpos = SET_BUCKET_NUMBER(i);    // Set bucket number
  156.     this->curpos |= SET_BUCKET_INDEX(0);    // Set index into bucket
  157.     return TRUE;                // Return success
  158.   }
  159. }
  160.     
  161.  
  162.  
  163.  
  164.  
  165. // prev -- Decrement current position. If INVALID, set to last
  166. // Input:  this*
  167. // Output: TRUE/FALSE
  168.  
  169. Boolean CoolBase_Hash_Table::prev () {
  170.   long prime = this->get_bucket_count ();    // Prime number of buckets
  171.   if (this->curpos == INVALID) {        // If INVALID current position
  172.     if (this->entry_count == 0)            // If no entries in table
  173.       return FALSE;                // Return failure
  174.     for (long i = prime-1; i >= 0; i--)        // For each bucket, search
  175.       if (this->get_count_in_bucket (i) != 0)    // If the bucket has an item
  176.     break;
  177.     this->curpos = SET_BUCKET_NUMBER (i);    // Set bucket number
  178.     this->curpos |= SET_BUCKET_INDEX ((this->get_count_in_bucket (i)-1));
  179.     return TRUE;                // Return success
  180.   }
  181.   else if (TRAVERSED(this->curpos))        // If already traversed set
  182.     return FALSE;                // Inidicate failure
  183.   else {
  184.     long hash = BUCKET_NUMBER(this->curpos);    // Get bucket number
  185.     long index = BUCKET_INDEX(this->curpos);    // Get index in bucket
  186.     if (index > 0) {                // If more items in bucket
  187.       this->curpos = SET_BUCKET_NUMBER (hash);    // Update bucket hash bits
  188.       this->curpos |= SET_BUCKET_INDEX ((index-1)); // Update bucket index bits
  189.       return TRUE;                // And return success
  190.     }
  191.     for (long i = hash-1; i >= 0; i--)        // For remaining buckets
  192.       if (this->items_in_buckets[i] != 0)    // If the bucket has an item
  193.     break;
  194.     if (i < 0) {                // If no more items
  195.       this->curpos = INVALID;            // Invalidate pointer
  196.       return FALSE;                // Return failure
  197.     }
  198.     this->curpos = SET_BUCKET_NUMBER(i);    // Set bucket number
  199.     this->curpos |= SET_BUCKET_INDEX((this->get_count_in_bucket (i)-1));
  200.     return TRUE;                // Return success
  201.   }
  202. }
  203.  
  204. // statistics -- Make a pass through the Hash Table and print out statistics
  205. //               for the number of entries in each bucket.
  206. // Input:   this*
  207. // Output   None
  208.  
  209. void CoolBase_Hash_Table::statistics () {
  210.   long arry[BUCKET_SIZE+1];
  211.   char str[30];
  212.   float pct_full;
  213.   for (int i = 0; i <= BUCKET_SIZE; i++)
  214.     arry[i]=0;
  215.   long buckets = get_bucket_count();
  216.   long total_slots = buckets * BUCKET_SIZE;
  217.  
  218.   for (i = 0; i < buckets; i++)         // For each bucket
  219.     arry[this->items_in_buckets[i] ]++;     //  Bump array per slots used
  220.  
  221.   // Print out general info
  222.   pct_full = (float)(entry_count*100.0) / (float)total_slots;
  223.   sprintf(str,"%.1f",pct_full);                 
  224.   cout << "\n" << buckets << " Buckets, " << BUCKET_SIZE << " slots each = "
  225.      << total_slots << " slots available.  " << entry_count << " slots used ("
  226.      << str << "%)\n";
  227.  
  228.   if(entry_count > 0) {                        // Print out slot usage
  229.     cout << "  Distribution of buckets with n slots filled:\n";
  230.     for (i = 0; i <= BUCKET_SIZE; i++) {
  231.       pct_full = (float)(arry[i]*100) / (float)buckets;
  232.       sprintf(str,"%.1f",pct_full);
  233.       cout << i << "=" << str << "% ";
  234.     }
  235.     cout << "\n\n";
  236.   }
  237. }
  238.  
  239. // clear -- Empty the hash table, but don't change allocated space
  240. // Input:   this*
  241. // Output   None
  242.  
  243. void CoolBase_Hash_Table::clear () {
  244.   for (int i = 0; i < hash_primes[this->current_bucket]; i++) // For each bucket
  245.     this->items_in_buckets[i] = 0;                  // Zero count
  246.   this->entry_count = 0;                      // Entries to 0
  247.   this->curpos = INVALID;                      // Invalid curpos
  248. }
  249.  
  250. // sxhash -- Hash function for char*
  251. // Input:    Character string
  252. // Output:    unsigned long hash value
  253.  
  254. unsigned long sxhash(const char* string) {
  255.   register unsigned long hash = *string++;
  256.   if(*string != END_OF_STRING) {
  257.     hash = (hash << 7) ^ *string++;
  258.     if (*string != END_OF_STRING) {
  259.       hash = (hash << 7) ^ *string++;
  260.       if (*string != END_OF_STRING) {
  261.     hash = (hash << 7) ^ *string++;
  262.     while (*string != END_OF_STRING) {// rotate hash left 7 bits & xor char
  263.     #ifdef DOS
  264.       hash = _lrotl(hash, 7) ^ *string++;
  265.     #else
  266.       long rest = hash >> 25;
  267.       hash = ((hash << 7) | rest) ^ *string++;
  268.     #endif
  269.     }
  270.       }
  271.     }
  272.   }
  273.   hash &= 0x7fffffffL;                // Make sure bit 32 is zero
  274.   return hash;
  275. }
  276.  
  277. Boolean charP_compare (char* const& s1, char* const& s2) {
  278.   return !strcmp (s1, s2);
  279. }
  280.  
  281.  
  282. // ratio_error -- Raise exception for CoolBase_Hash_Table::set_growth_ratio()
  283. // Input:         Bad ratio specification
  284. // Output:        None
  285.  
  286. void CoolBase_Hash_Table::ratio_error (float r) {
  287.   //RAISE (Error, SYM(CoolBase_Hash_Table), SYM(Negative_Ratio),
  288.   printf ("CoolBase_Hash_Table::set_growth_ratio(): Negative growth ratio %f.\n", r);
  289.   abort ();
  290. }
  291.  
  292.  
  293. // resize_error -- Raise exception for CoolBase_Hash_Table::resize()
  294. // Input:          Bad size specification
  295. // Output:         None
  296.  
  297. void CoolBase_Hash_Table::resize_error (const char* T1, const char* T2, long s) {
  298.   //RAISE (Error, SYM(CoolBase_Hash_Table), SYM(Negative_Size),
  299.   printf ("CoolBase_Hash_Table<%s,%s>::resize(): Negative resize %d.\n", T1, T2, s);
  300.   abort ();
  301. }
  302.  
  303.  
  304. // value_error -- Raise exception for CoolBase_Hash_Table::value()
  305. // Input:        None
  306. // Output:       None
  307.      
  308. void CoolBase_Hash_Table::value_error (const char* T1, const char* T2) {
  309.   //RAISE (Error, SYM(CoolBase_Hash_Table), SYM(Invalid_Cpos),
  310.   printf ("CoolBase_Hash_Table<%s,%s>::value(): Invalid current position.\n", T1, T2);
  311.   abort ();
  312. }
  313.  
  314.  
  315. // key_error -- Raise exception for CoolBase_Hash_Table::key()
  316. // Input:       None
  317. // Output:      None
  318.      
  319. void CoolBase_Hash_Table::key_error (const char* T1, const char* T2) {
  320.   //RAISE (Error, SYM(CoolBase_Hash_Table), SYM(Invalid_Cpos),
  321.   printf ("CoolBase_Hash_Table<%s,%s>::key(): Invalid current position.\n", T1, T2);
  322.   abort ();
  323. }
  324.  
  325.  
  326. // remove_error -- Raise exception for CoolBase_Hash_Table::remove()
  327. // Input:          Bad lookup value
  328. // Output:         None
  329.  
  330. void CoolBase_Hash_Table::remove_error (const char* T1, const char* T2) {
  331.   //RAISE (Error, SYM(CoolBase_Hash_Table), SYM(Invalid_Cpos),
  332.   printf ("CoolBase_Hash_Table<%s,%s>::remove(): Invalid current position.\n", T1, T2);
  333.   abort ();
  334. }
  335.